#! /usr/bin/python
import glob, sys, os
import DebugMsgDef

####################################################
## Parsing forwarding path and routing efficiency ##
####################################################

##Goals:
##Find the forwarding path of all messages and compute routing efficient for all forwarding nodes
##
##Steps:
##1) Find the forwarding node for a sent messages.
##2) Find the all overheard node for the sent messages.
##3) Find the path cost of the forwarding nodes and the overhead node (near the forwarding time)
##4) Compute routing efficiency = min cost / forwarding cost
##5) Write forwarding path, cost per hop, path cost of {forwarding }


DEFAULT_TIME_GAP = 1000 * 20

def readFile(fn):
    """
    Read csv files.
    Return: node list, a dict of message list.
    """
    nodeID = int(fn[fn.find('node') + 4:-4])
    msgList = []
    print 'Reading', fn
    dfile = open(fn)
    aline = dfile.readline()
    if 'NET_C_' not in aline:
        print 'Found uncovered csv files. converting...'
        dfile.close()
        import dec2hex
        dec2hex.type2String(fn)
        dfile = open(fn)
    else:
        dfile.seek(0)
    timeLast = 0
    for aline in open(fn):
        msg = SerialMessage(aline)
        msgList.append(msg)
        if timeLast > getTime(msg):
            print "Error in read file: server time no increase!"
        timeLast = getTime(msg)
    print len(msgList), 'message found.'
    return nodeID, msgList


def categorizeMessage(msgList):
    """
    Categorize messages according to the msg type.
    returned value:
        A dict, key=msg Type (stirng), value=list of msg of key type.
    """
    tp = DebugMsgDef.debugMsgTypes.values()
    ep = [[] for i in range(len(DebugMsgDef.debugMsgTypes))]
    msgCata = dict(zip(tp,ep))
    for i in xrange(len(msgList)):
        msgCata[getType(msgList[i])].append(i)
    return msgCata


def organizeTxMessage(msgList):
    """
    Organize the msg list (of a node) such that:
    1) origin dict, key=origin node id, value=tx dict for the origin
    2) tx dict, key=seq id, value=list of tx msgs of the key msg
    A seq id is assigned to a set of packets that has
     -- same origin
     -- same seq
     -- temproal division < 200*send interval
     seq id = seq + 256 * number of warp around
    """
    origDict = dict()         # dict of origin:txDict
    tmpOrigDict = dict()
    numWarpDict = {}    # dict of warp around, origin:# of warp
    txDict = {}             # dict of tx under one seq, seqid:list of tx msg
    seqTimeDict = {}    # dict of the first/last time of appearence of a msg with seq. sqe:[first,last]
    firstTimeIdx = 1
    lastTimeIdx = 2
    txTotal = 0

    # first classify all the msgs with the same orig.
    for msgIdx in xrange(len(msgList)):
        msg = msgList[msgIdx]
        if getType(msg) in DebugMsgDef.TxMessageTypes:
            txTotal += 1
            origin = getOrigin(msg)
            if origin in tmpOrigDict:
                tmpOrigDict[origin].append(msgIdx)
            else:
                tmpOrigDict[origin] = [msgIdx]
    print len(tmpOrigDict), 'orig found,'
    # Then for each orig, compute the # of warp and real seq.
    MAX_SEQ = 256
    SEQ_DIST_THRESH = MAX_SEQ / 2
    for origin,txMsgList in tmpOrigDict.items():
        numWarp = 0     # num. of warp
        lastSeq = getSeq(msgList[txMsgList[0]]) # get seq of the first tx msg
        seqSinceLastWarp = set() # unique seqs since last warp.
        numInterleaved = 0             # number of interleaved msgs.
        sortedMsgs = dict()            # a msg dict, realseq:list of msg idx
        for msgIdx in txMsgList:
            seq = getSeq(msgList[msgIdx])
            msgTime = getTime(msgList[msgIdx])
            seqDiff = seq - lastSeq
            if seqDiff < -SEQ_DIST_THRESH:
                if len(seqSinceLastWarp) > SEQ_DIST_THRESH:
                    print 'Warp @', msgIdx, 'Num of unique seq so far:', len(seqSinceLastWarp)
                    numWarp = numWarp + 1
                    seqSinceLastWarp = set()
                    realSeq = seq + MAX_SEQ * numWarp
                else:
                    # early warp -> caused by interleaved msg near warp point.
                    realSeq = seq + MAX_SEQ * numWarp
                    numInterleaved = numInterleaved + 1
            elif seqDiff < 0:
                # interleaved msgs
                numInterleaved = numInterleaved + 1
                realSeq = seq + MAX_SEQ * numWarp
            elif seqDiff <= SEQ_DIST_THRESH:
                realSeq = seq + MAX_SEQ * numWarp
            else: # seqDiff > SEQ_DIST_THRESH
                if len(seqSinceLastWarp) > SEQ_DIST_THRESH:
                    # big seq jump; lost a lot of pkt?
                    realSeq = seq + MAX_SEQ * numWarp
                else:
                    # interleaved msgs near warp point
                    realSeq = seq + MAX_SEQ * (numWarp - 1)
            seqSinceLastWarp.add(seq)
            # print 'Seq', seq, 'Last Seq', lastSeq, 'Diff', seqDiff,'lastWarp', len(seqSinceLastWarp), 'Real', realSeq
            if realSeq in sortedMsgs:
                sortedMsgs[realSeq].append(msgIdx)
            else:
                sortedMsgs[realSeq] = [msgIdx]
            lastSeq = seq
        # finish iter for a originate node
        print 'Finish orig', origin, 'Total msg', len(txMsgList), 'Interleaved msg:', numInterleaved, 'Real seq', len(sortedMsgs)
        origDict[origin] = sortedMsgs
    return txTotal, origDict

def findSnoopMsg(msgList, seq, origin, src, msgTime, startIdx):
    """
    Find the first SNOOP/PD msgs from the msgList starting startIdx
    """
    MSG_TIME_GAP = 10000  # 10 seconds is a big enough gap
    BIG_MSG_STEP = 10
    # check startIdx time to decide what is the direction to search
    currIdx = startIdx
    currTime = getTime(msgList[currIdx])
    # jump 10 msg a time until pass msgTime - GAP line
    # msgT < currT -> search up (time decrease)
    # msgT > currT -> search down (time increase)
    BIG_MSG_STEP = 10 if msgTime > currTime else -10
    SMALL_MSG_STEP = 1 if msgTime > currTime else -1
    # skip by big_step
    while abs(currTime - msgTime) > MSG_TIME_GAP:
      currIdx = currIdx + BIG_MSG_STEP
      if currIdx < 0 or currIdx >= len(msgList):
        # msg not found
        return 0
      currTime = getTime(msgList[currIdx])
    # and then search the time
    minTimeDiff = abs(currTime - msgTime)
    snoopMsgIdx = -1
    while abs(currTime - msgTime) <= MSG_TIME_GAP:
      if getType(msgList[currIdx]) in DebugMsgDef.TxSnoopMessages:
        if getSeq(msgList[currIdx]) == seq \
          and getOrigin(msgList[currIdx])== origin \
          and getSrc(msgList[currIdx]) == src:
          if abs(currTime - msgTime) < minTimeDiff:
            minTimeDiff = timeDiff


          print 'haha'


      currIdx = currIdx + SMALL_MSG_STEP
      if currIdx < 0 or currIdx >= len(msgList):
        # msg not found
        return 0
      currTime = getTime(msgList[currIdx])



    print 'haha'

def packetPath(msgDict, txMsgDict, rootID):
    """
    Trace packet path -- simply find all nodes that have messages about the
    origin node.
    """
    pathDict={}
    for origin, origmsgList in msgDict.items():
        if origin == rootID:
            continue
        pathDict[origin] = {}
        seqList = [] # list of unique seq (seq id)
        pathList = [] # list of pktTuple, hop, tx, status

        # first the seq of pkt sent from originate node
        if origin in txMsgDict:
            origDict = txMsgDict[origin]
            if origin in origDict:
                seqDict = origDict[origin] # pkt originated from the origin
                seqList = sorted(seqDict.keys())

        # then find all nodes that has the same (origin, seqid)
        for seqid in seqList:
            pathStatus = 'LOST'
            realSeq = seqid % 1000
            # put in the originate node first
            hopList = [origin]
            txList = [countTxSendMessage(txMsgDict[origin][origin][seqid], origmsgList)]

            sentTime = getTime(origmsgList[txMsgDict[origin][origin][seqid][0]])
            sentMsg = origmsgList[txMsgDict[origin][origin][seqid][0]]


            for nodeID , msgList in msgDict.items():
                if nodeID == origin:
                    continue
                origDict = txMsgDict[nodeID]
                # print 'tracking', seqid, 'for node', origin, '@',nodeID
                if origin in origDict:
                    seqDict = origDict[origin]
                    # search all seqid that has the real seq, starting from the lowest ones
                    correctSID = -1
                    for sid in sorted(seqDict.keys()):
                        if sid % 1000 == realSeq:
                            tmpList = seqDict[sid] # list of msg idx with the same origin, seq.
                            rcvTime = getTime(msgList[tmpList[0]])
                            # print 'time diff for seqid', seqid, rcvTime - sentTime, 'sid', sid, 'node', nodeID
                            if rcvTime - sentTime < -DEFAULT_TIME_GAP/2:
                                continue
                            elif rcvTime - sentTime < DEFAULT_TIME_GAP/2:
                                # found one match. check multiple found.
                                if correctSID != -1:
                                    print 'Screwed: multple packet group match.', origin, nodeID
                                    sys.exit(0)
                                correctSID = sid
                                # print 'Found match!', sid
                            else: # if the timediff is larger default time gap, skip.
                                break
                    # should find the only match if correctSID != -1.
                    # If not found, do nothing.
                    if correctSID != -1:
                        hopList.append(nodeID)
                        txList.append(countTxSendMessage(seqDict[correctSID], msgList))
                        if nodeID == rootID:
                            pathStatus = 'DELIVERED'
                            deliveredTime = getTime(msgList[seqDict[correctSID][0]])
                            deliverMsg = msgList[seqDict[correctSID][0]]

                        # delete the found (not yet)
            if pathStatus == 'DELIVERED' and deliveredTime - sentTime > DEFAULT_TIME_GAP:
                print 'Warning: delivered time much greater than sent time: ', (deliveredTime - sentTime)/1000, DEFAULT_TIME_GAP/1000
                print 'sent', sentMsg
                print 'delivered', deliverMsg
                print getSeq(sentMsg), getSeq(deliverMsg)
            msg = origmsgList[txMsgDict[origin][origin][seqid][0]]
            pktTuple = (getSeq(msg), getOrigin(msg), getTime(msg))
            pathList.append((pktTuple, hopList, txList, pathStatus))

        pathDict[origin] = pathList
        print 'parsed', len(pathList), 'pkts for', origin

    return pathDict

def writePath(pathDict, surfix):
    """
    Put the path to file!
    """
    # clean the directory
    for fn in glob.glob(surfix + '*'):
        os.remove(fn)

    # summary: node,# pkt, avgr. PL, delivered, lost, loop
    sumDict={}
    sumpkt = 0; sumpl=0.0; sumtx=0;sumdlv=0; sumlost=0; sumloop=0
    for nodeID in pathDict.keys():
        pathList = pathDict[nodeID]
        sumDict[nodeID] = [nodeID,len(pathList)]
        pl=0.0; tx=0; dlv=0; lost=0; loop=0

        pathFile = open(surfix + str(nodeID), 'w')
        for (pktTuple, hopList, txList, status) in pathList:
            pl += len(hopList)
            tx += sum(txList)
            if status == 'DELIVERED':
                dlv += 1
            elif status == 'LOST':
                lost += 1
            elif status == 'LOOP':
                loop += 1
            else:
                print 'Invaild path status!'
            pathStr = ';'.join([ status, \
                                                    ','.join(str(i) for i in pktTuple), \
                                                    ','.join(str(i) for i in hopList),    \
                                                    ','.join(str(i) for i in txList), \
                                                    `len(hopList)`, `sum(txList)`, \
                                                    `max(txList)`, `min(txList)`])
            pathFile.write(pathStr+'\n')
        pathFile.close()
        sumpkt+=len(pathList);sumpl+=pl; sumtx+=tx; sumdlv+=dlv; sumlost+=lost; sumloop+=loop
        if (len(pathList) > 0):
            sumDict[nodeID].extend([pl / float(len(pathList)), tx, dlv,lost,loop])
        else:
            sumDict[nodeID].extend([ 0, tx, dlv,lost,loop])
    # also a summary file
    nodes = sumDict.keys()
    nodes.sort()
    if (sumpkt > 0):
        sumStr = ','.join(str(i) for i in [-1,sumpkt, sumpl/sumpkt, sumtx, sumdlv, sumlost, sumloop])
    else:
        sumStr = ','.join(str(i) for i in [-1,sumpkt, 0, sumtx, sumdlv, sumlost, sumloop])

    for nodeID in nodes:
        sumStr += '\n' + ','.join([str(i) for i in sumDict[nodeID]])
    pathFile = open(surfix + '_summary','w')
    pathFile.write(sumStr)
    pathFile.close()



def countTxSendMessage(msgIdx, msgList):
    """
    simply count the number of tx send messages of a msg list
    """
    cnt = 0
    for msgID in msgIdx:
        if getType(msgList[msgID]) in DebugMsgDef.TxSendMessages:
            cnt += 1
    return cnt


def writeSummary(msgType, fn):
    """
    Generate a csv file, list useful types of debug messages
    and their occurances.
    """
    types = DebugMsgDef.TxMessageTypes
    types.extend(DebugMsgDef.TreeMessageTypes)
    types.extend(DebugMsgDef.PdMessageTypes)
    sumStr = 'NodeID,' + ','.join(types) + '\n'
    nodes = msgType.keys()
    nodes.sort()
    for nodeID in nodes:
        msgDict = msgType[nodeID]
        sumStr += str(nodeID) + ','
        sumStr += ','.join([str(len(msgDict[tp])) for tp in types]) + '\n'
    sumFile = open(fn, 'w')
    sumFile.write(sumStr)
    sumFile.close()


def main():
    """
    Main method
    """
    datadir = sys.argv[1]
    if datadir[-1] != '/':
        datadir = datadir + '/'

    csvlist = glob.glob(datadir + 'node*.csv')
    if len(csvlist) == 0:
        print "No csv files in the directory:", sys.argv[1]
        sys.exit(0)

    rootID = int(sys.argv[2])

    nodeList = []             # list of nodes
    msgDict = {}                # key: node ID, value: list of msg
    txMsgDict = {}            # key: node ID, value: organized tx messages
    msgTypeDict = {}        # key: node ID. value: dict(msg type, msg idx)
    for csvfile in csvlist:
        nodeID, msgList = readFile(csvfile)
        if len(msgList) == 0:
            print 'Empyt file:', csvfile
            continue
        nodeList.append(nodeID)
        msgDict[nodeID]=msgList
        print 'Categorizing messages for node', nodeID, '... ',
        msgTypeDict[nodeID] = categorizeMessage(msgList)
        print 'done'

        print 'Organizing Tx messages for node', nodeID, '... '
        txTotal, txMsgDict[nodeID] = organizeTxMessage(msgList)
        print 'found', txTotal, 'tx msgs from', len(txMsgDict[nodeID]), 'origins.'

    print len(nodeList), 'files read.'


    # start compute path. need:
    # 1) summary of debug msg: send, pd, and snoop(ones has better ETX)
    # 2) packet path, TX spend on each nodes, total TX, and TX of TP.
    # 3) save the summary and packet path to MATLAB readable format.

    #~ writeSummary(msgTypeDict, datadir + 'summary')
    #~ pathDict = packetPath(msgDict, txMsgDict, rootID)
    #~ writePath(pathDict, datadir + 'path')


######## ENTRTY #######
if(len(sys.argv) != 3):
    print 'parserMain <data dir> <root id>'
    sys.exit(0)

# determine what kind of messages based on dir name :P
if 'orig' in sys.argv[1]:
    from DebugMsgList_Original import *
    ORIGINAL = True
else:
    from DebugMsgList_Modified import *
    ORIGINAL = False

#~ DEFAULT_TIME_GAP = int(200 * 1000 * float(sys.argv[3])) # time gap before warp around
#~ print DEFAULT_TIME_GAP

if __name__ == '__main__': main()

